<!DOCTYPE html>
<html lang="">

<head>
	<meta name="generator" content="Hugo 0.73.0" />
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<meta name="author" content="Ap Chen ">
<meta name="description" content="进程调度和线程调度通常是可替换的 多核系统比单核系统在进程等待时运行更有效率 调度算法 关注的进程性能：CPU执行转数、 I/O等待 算法实现关键：A" />
<meta name="keywords" content="blog" />
<meta name="robots" content="noodp" />

<link rel="canonical" href="https://fziks.gitee.io/notes/operating-system/osc-chapt.5/" />

<meta itemprop="name" content="OSC Chapt.5">
<meta itemprop="description" content="进程调度和线程调度通常是可替换的 多核系统比单核系统在进程等待时运行更有效率 调度算法 关注的进程性能：CPU执行转数、 I/O等待 算法实现关键：A">
<meta itemprop="datePublished" content="2020-06-26T00:00:00&#43;00:00" />
<meta itemprop="dateModified" content="2020-06-26T00:00:00&#43;00:00" />
<meta itemprop="wordCount" content="1023">



<meta itemprop="keywords" content="os,notes," />
<meta property="og:title" content="OSC Chapt.5" />
<meta property="og:description" content="进程调度和线程调度通常是可替换的 多核系统比单核系统在进程等待时运行更有效率 调度算法 关注的进程性能：CPU执行转数、 I/O等待 算法实现关键：A" />
<meta property="og:type" content="article" />
<meta property="og:url" content="https://fziks.gitee.io/notes/operating-system/osc-chapt.5/" />
<meta property="article:published_time" content="2020-06-26T00:00:00+00:00" />
<meta property="article:modified_time" content="2020-06-26T00:00:00+00:00" />

<meta name="twitter:card" content="summary"/>
<meta name="twitter:title" content="OSC Chapt.5"/>
<meta name="twitter:description" content="进程调度和线程调度通常是可替换的 多核系统比单核系统在进程等待时运行更有效率 调度算法 关注的进程性能：CPU执行转数、 I/O等待 算法实现关键：A"/>


<link rel="apple-touch-icon" sizes="60x60" href="https://fziks.gitee.io/icons/apple-touch-icon.png">
<link rel="icon" type="image/png" sizes="32x32" href="https://fziks.gitee.io/icons/favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="https://fziks.gitee.io/icons/favicon-16x16.png">
<link rel="manifest" href="https://fziks.gitee.io/icons/site.webmanifest">
<link rel="mask-icon" href="https://fziks.gitee.io/icons/safari-pinned-tab.svg" color="#5bbad5">
<link rel="shortcut icon" href="https://fziks.gitee.io/icons/favicon.ico">
<meta name="msapplication-TileColor" content="#ffffff">
<meta name="msapplication-config" content="/icons/browserconfig.xml">
<meta name="theme-color" content="#ffffff">

<title>OSC Chapt.5</title>


<link rel="stylesheet" href="//at.alicdn.com/t/font_1559566_wk214kwa2dn.css">


    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.11.1/dist/katex.min.css" integrity="sha384-zB1R0rpPzHqg7Kpt0Aljp8JPLqbXI3bhnPWROx27a9N0Ll6ZP/+DiW/UqRcLbRjq" crossorigin="anonymous">



    
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/normalize/8.0.1/normalize.css" integrity="sha256-WAgYcAck1C1/zEl5sBl5cfyhxtLgKGdpI3oKyJffVRI=" crossorigin="anonymous" />
    
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/animate.css/3.7.2/animate.css" integrity="sha256-a2tobsqlbgLsWs7ZVUGgP5IvWZsx8bTNQpzsqCSm5mk=" crossorigin="anonymous" />
    
   <link href="https://stackpath.bootstrapcdn.com/bootswatch/4.4.1/materia/bootstrap.min.css" rel="stylesheet" integrity="sha384-1tymk6x9Y5K+OF0tlmG2fDRcn67QGzBkiM3IgtJ3VrtGrIi5ryhHjKjeeS60f1FA" crossorigin="anonymous">
    
    
    <link rel="stylesheet" href="https://fziks.gitee.io/sass/main_cdn.min.270b43bb8631af4497ed45b90db42c517e86c9511418de9152f134d02ed32b87.min.2192baea245cf318085511589e62bfbdb3fbe4fb0eef718f1be9af91c10542ce.css" integity="sha256-IZK66iRc8xgIVRFYnmK/vbP75PsO73GPG&#43;mvkcEFQs4=">

</head>

<body style="overflow-x: unset;">
	<div class="container-fluid">
		<div class="row d-print-block">
			<div class="col-12 col-md-3 col-lg-2 bd-sidebar d-print-none">
				<div class="d-flex mt-3 border-bottom">
        <span class="navbar-brand w-100" style="display: grid;">
            <small>
                <a href="https://fziks.gitee.io/" class="text-black-50">
                    <i class="iconfont icon-back-arrow-"></i>
                </a>
                Ap Chen's
            </small>
            <a class="text-dark" href="https://fziks.gitee.io/notes/">
                Notes
            </a>
        </span>
        <button class="btn btn-link text-dark d-md-none p-0 ml-3" type="button" data-toggle="collapse"
            data-target="#bd-docs-nav" aria-controls="bd-docs-nav" aria-expanded="true"
            aria-label="Toggle docs navigation">
            <i class="fad fa-bars"></i>
        </button>
    </div>
				<nav id="bd-docs-nav" class="collapse bd-links">
    
    
    
    <div class="bd-toc-item">
        <a class="bd-toc-link" href="https://fziks.gitee.io/notes/computer-network/">
            
            
                <span class="icontext">S</span>
            
            
            计算机网络
        </a>
    </div>
    
    
    
    <div class="bd-toc-item active bg-light">
        <a class="bd-toc-link" href="https://fziks.gitee.io/notes/operating-system/">
            <i class="iconfont icon-back-arrow-reverse"></i>
            操作系统
        </a>
        <ul class="nav bd-sidenav">
            
            
            <li>
                <a href="https://fziks.gitee.io/notes/operating-system/process-management/">Process Management</a>
            </li>
            
            
            
            <li class="active">
                <a href="https://fziks.gitee.io/notes/operating-system/osc-chapt.5/">
                    <i class="fad fa-chevron-right mr-1"></i>
                    OSC Chapt.5
                </a>
            </li>
            
            
            
            <li>
                <a href="https://fziks.gitee.io/notes/operating-system/os-persistance/">Persistance</a>
            </li>
            
            
        </ul>
    </div>
    
    
    
    <div class="bd-toc-item">
        <a class="bd-toc-link" href="https://fziks.gitee.io/notes/database/">
            
            
                <span class="icontext">S</span>
            
            
            数据库
        </a>
    </div>
    
    
    
    <div class="bd-toc-item">
        <a class="bd-toc-link" href="https://fziks.gitee.io/notes/cs50-introduction-to-computer-science/">
            
            
                <span class="icontext">S</span>
            
            
            CS50 MIT
        </a>
    </div>
    
    
    
    <div class="bd-toc-item">
        <a class="bd-toc-link" href="https://fziks.gitee.io/notes/advanced-programming/">
            
            
                <span class="icontext">A</span>
            
            
            高级程序设计
        </a>
    </div>
    
    
    
    <div class="bd-toc-item">
        <a class="bd-toc-link" href="https://fziks.gitee.io/notes/deep-learning/">
            
            
                <span class="icontext">O</span>
            
            
            深度学习基础
        </a>
    </div>
    
    
    
    <div class="bd-toc-item">
        <a class="bd-toc-link" href="https://fziks.gitee.io/notes/%E6%96%87%E7%8C%AE%E7%AE%A1%E7%90%86%E4%B8%8E%E4%BF%A1%E6%81%AF%E5%88%86%E6%9E%90/">
            
            
                <span class="icontext">O</span>
            
            
            文献管理与信息分析
        </a>
    </div>
    
    
</nav>
			</div>
			<div class="col-12 col-md-9 col-lg-10 d-print-block">
				<div class="row d-print-block">
					<main class="col-12 col-md-10 col-lg-9 py-md-3 pl-md-5 bd-content d-print-block" role="main">
						<div id="title" class="my-4 border-bottom">
							<span>操作系统</span>
							<h2>OSC Chapt.5</h2>
							<footer>
								<span>
									<i class="iconfont icon-NewFile mr-2"></i>
									2020-06-26 08:00 CST
								</span> <br />
								<span>
									<i class="iconfont icon-modify mr-2"></i>
									2020-06-26 08:00 CST
								</span> <br />
								<span>
									<i class="iconfont icon-copyright mr-2"></i>
									CC BY-NC 4.0
								</span>
							</footer>
						</div>
						<div id="content" class="hl-h2">
							
							
							
							
							
							
							
							
							
							
							
							
							<ul>
<li>进程调度和线程调度通常是可替换的</li>
<li>多核系统比单核系统在进程等待时运行更有效率</li>
</ul>
<h2 id="调度算法">调度算法<a href="#调度算法" class="anchor" aria-hidden="true"><i class="iconfont icon-link"></i></a></h2>
<ul>
<li>关注的进程性能：CPU执行转数、 I/O等待</li>
<li>算法实现关键：An I/O-bound program typically has many short CPU bursts. A CPU-bound program might have a few long CPU bursts.</li>
<li>在四种情况下发生：1running to waiting 、2running to ready 、3waiting to ready 、 4terminates</li>
<li>1、4不剥夺，2、3是剥夺</li>
</ul>
<h2 id="单核调度算法">单核调度算法<a href="#单核调度算法" class="anchor" aria-hidden="true"><i class="iconfont icon-link"></i></a></h2>
<h3 id="first-come-first-served-fcfs">First Come, First Served (FCFS)<a href="#first-come-first-served-fcfs" class="anchor" aria-hidden="true"><i class="iconfont icon-link"></i></a></h3>
<p>实现简单，不适合交互系统</p>
<p>但如果每个任务所需时间不同，FIFO的效果就很差。大部分小的任务排在了一个大任务的后面，称为<strong>护卫效应</strong>(convoy effect)。</p>
<h3 id="shortest-job-first-sjf">Shortest Job First (SJF)<a href="#shortest-job-first-sjf" class="anchor" aria-hidden="true"><i class="iconfont icon-link"></i></a></h3>
<p>严格意义上为Shortest-next-CPU-burst algorithm，选择下一个更短的CPU burst进程，如果两进程相同则FCFS。</p>
<p>因为我们假设所有任务同时到来，所以在这个条件下可以保证SJF是最优调度算法（贪心）。</p>
<ul>
<li>剥夺（一般效果更好）和非剥夺式</li>
<li>优化了平均等待时间，但未实现等级调度</li>
</ul>
<p>预测公式 $\tau_{n+1} = \alpha t_n + (1-\alpha)\tau_n$</p>
<p>$\alpha$是<strong>最近</strong>和<strong>历史</strong>的权重比，取值小于1。If 0 then 与最近无关联 ；If 1/2 then最近和历史权重相等</p>
<p>$t_n$是最近信息， $\tau_n$是历史记录。</p>
<h3 id="round-robinrr"><strong>Round Robin</strong>(RR)<a href="#round-robinrr" class="anchor" aria-hidden="true"><i class="iconfont icon-link"></i></a></h3>
<p>每次花一段时间(time slice/scheduling quantum)执行一个任务，然后切换到队列的下一个任务。因此，RR也被叫做<strong>time-slicing</strong>。</p>
<p>对于RR算法来说，决定一次运行的时间是非常重要的。运行时间越短，在响应时间标准下RR效果越好，但切换上下文的开销会拖累总体的性能。因此，时间切片的长度是一个trade-off，时间长可以<strong>均摊</strong>(amortize)切换上下文的开销。</p>
<blockquote>
<h5 id="tip-amortization-can-reduce-costs">TIP: Amortization Can Reduce Costs<a href="#tip-amortization-can-reduce-costs" class="anchor" aria-hidden="true"><i class="iconfont icon-link"></i></a></h5>
<p>The general technique of <strong>amortization</strong> is commonly used in systems when there is a ﬁxed cost to some operation. By incurring that cost less often (i.e., by performing the operation fewer times), the total cost to the system is reduced. For example, if the time slice is set to 10 ms, and the context-switch cost is 1 ms, roughly 10% of time is spent context switching and is thus wasted. If we want to <em>amortize</em> this cost, we can increase the time slice, e.g., to 100 ms. In this case, less than 1% of time is spent context switching, and thus the cost of time-slicing has been amortized.</p>
</blockquote>
<p>但是RR在完成时间上并不是一个高效的策略，甚至比FIFO还差。</p>
<p>笼统地说，任何通过划分CPU执行时间来保持<strong>公平</strong>的调度算法都在完成时间上效果不咋地。实际上，这是一个内在的trade-off：如果你要不公平，你可以让跑得快的任务早点完成，但是响应时间就很长；否则，你要减少响应时间，完成时间就会很长。此类<strong>trade-off</strong>在系统中非常常见，鱼和熊掌不可兼得。</p>
<p>至此，共有两类调度算法：第一类(SJF, STCF)优化完成时间，但响应时间高；第二类(RR)优化响应时间，但完成时间长。</p>
<p>其中STCF（Short Time to Complete First）</p>

						</div>
					</main>
					<div class="d-none d-lg-block col-lg-3 bd-toc d-print-none">
						<div class="btn-group-vertical w-100 my-3">
    
    <a class="btn btn-outline-secondary text-dark w-100 p-2" href="https://list.html" target="_blank">
        <i class="iconfont icon-LC_icon_list_line"></i><br />待更新列表
    </a>
    

    
    <a class="btn btn-outline-secondary text-dark w-100 p-2" href="mailto:littlegreedy@qq.com"
        target="_blank">
        <i class="iconfont icon-discussion"></i><br />纠错与咨询
    </a>
    
    
    
    
        <a class="btn btn-outline-secondary text-dark w-100 p-2" href="#" onclick="window.print()">
            <i class="iconfont icon-dayin"></i><br />打印本页
        </a>
    
    
</div>
						<h4 class="card-title pb-0">目录</h4>
						<nav id="TableOfContents">
  <ul>
    <li><a href="#调度算法">调度算法</a></li>
    <li><a href="#单核调度算法">单核调度算法</a>
      <ul>
        <li><a href="#first-come-first-served-fcfs">First Come, First Served (FCFS)</a></li>
        <li><a href="#shortest-job-first-sjf">Shortest Job First (SJF)</a></li>
        <li><a href="#round-robinrr"><strong>Round Robin</strong>(RR)</a></li>
      </ul>
    </li>
  </ul>
</nav>
						
						
						<div id="disqus_thread"></div>
							<script>
							

							

							(function() { 
							var d = document, s = d.createElement('script');
							s.src = "https://"+"your site name on disqus"+".disqus.com/embed.js";
							s.setAttribute('data-timestamp', +new Date());
							(d.head || d.body).appendChild(s);
							})();
							</script>
							<noscript>Please enable JavaScript to view the <a href="https://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>                  
					  	</div>
						
					</div>
				</div>
			</div>
		</div>
	</div>

	<script
    src="https://code.jquery.com/jquery-3.4.1.min.js"
    integrity="sha256-CSXorXvZcTkaix6Yvo6HppcZGetbYMGWSFlBw8HfCJo="
    crossorigin="anonymous"></script><script src="https://cdnjs.cloudflare.com/ajax/libs/popper.js/1.14.7/umd/popper.min.js" integrity="sha384-UO2eT0CpHqdSJQ6hJty5KVphtPhzWj9WO1clHTMGa3JDZwrnQq4sF86dIHNDz0W1" crossorigin="anonymous"></script>
    <script src="https://stackpath.bootstrapcdn.com/bootstrap/4.3.1/js/bootstrap.min.js" integrity="sha384-JjSmVgyd0p3pXB1rRibZUAYoIIy6OrQ6VrjIEaFf/nJGzIxFDsf4x0xIM+B07jRM" crossorigin="anonymous"></script><script defer src="https://cdn.jsdelivr.net/npm/katex@0.11.1/dist/katex.min.js" integrity="sha384-y23I5Q6l+B6vatafAwxRu/0oK/79VlbSz7Q9aiSZUvyWYIYsd+qj+o24G5ZU2zJz" crossorigin="anonymous"></script>
<script defer src="https://cdn.jsdelivr.net/npm/katex@0.11.1/dist/contrib/auto-render.min.js" integrity="sha384-kWPLUVMOks5AQFrykwIup5lo0m3iMkkHrD0uJ4H5cjeGihAutqP0yW0J6dpFiVkI" crossorigin="anonymous"
onload="renderMathInElement(document.body);"></script>

<script type="text/javascript" src="https://fziks.gitee.io/custom.min.d3e1b7647f32dbe7e0140398739a26dad3f3470fc1eebe0741ef33668f1b7bd0b2917dc6efb9f0d9f1092b91dca502cab1b883863f02530133a8a8ef609926af.js" integrity="sha512-0&#43;G3ZH8y2&#43;fgFAOYc5om2tPzRw/B7r4HQe8zZo8be9CykX3G77nw2fEJK5HcpQLKsbiDhj8CUwEzqKjvYJkmrw=="></script>
<script type="text/javascript">

document.addEventListener("DOMContentLoaded", function () {
    renderMathInElement(
        document.body, {
            delimiters: [
                {
                    left: "$$",
                    right: "$$",
                    display: true
                },
                {
                    left: "\\[",
                    right: "\\]",
                    display: true
                },
                {
                    left: "$",
                    right: "$",
                    display: false
                },
                {
                    left: "\\(",
                    right: "\\)",
                    display: false
                }
            ],
            strict: false
        }
    );
});


$(document).on('click', 'a[href^="#"]', function (event) {
    event.preventDefault();

    $('html, body').animate({
        scrollTop: $($.attr(this, 'href')).offset().top
    }, 500);
});
</script>




</body>

</html>